package basic.study.algorithms.solution.mergesort;

import java.util.*;

/**
 * @author Kevin
 * @date 2020/2/17 15:56
 * 分治—最近点对问题
 * 在二维平面上的n个点中，如何快速的找出最近的一对点，就是最近点对问题
 */
public class NearestPoint {

//    public static boolean sortByX(Point p1, Point p2) {//根据x坐标从小到大排序
//        if (p1.x == p2.x){
//            return p1.y < p2.y;
//        }
//        return p1.x < p2.x;
//    }
//
//    public static boolean sortByY(Point p1, Point p2) {
//        return p1.y < p2.y;
//    }

    public static double getDistance(Point p1, Point p2) {
        double dis_x = p1.x - p2.x;
        double dis_y = p1.y - p2.y;
        return Math.sqrt(dis_x * dis_x + dis_y * dis_y);
    }

    public static double getMin(ArrayList<Point> list, int low, int high) {
        if (high - low == 1) {//两个结点
            return getDistance(list.get(low), list.get(high));
        } else if (high - low == 2) {//3个节点
            double dist1 = getDistance(list.get(low), list.get(low+1));
            double dist2 = getDistance(list.get(low), list.get(low+2));
            double dist3 = getDistance(list.get(low+1), list.get(low+2));
            return Math.min(Math.min(dist1, dist2), dist3);
        } else {
            int mid = low + (high - low) >> 1;
            double left_min = getMin(list, low, mid);
            double righr_min = getMin(list, mid+1, high);
            double d = Math.min(left_min, righr_min);
            ArrayList<Point> res = new ArrayList<>();
            int i,j,k = 0;
            for (i = 0; i <= high; i++) {
                //此时mid是左边区块的最后一点，最接近mid中线
                if (Math.abs(list.get(mid).x - list.get(i).x) < d) {
                    res.add(list.get(i));
                }
            }
            res.sort(new Comparator<Point>() {//根据纵坐标从小到大排序
                @Override
                public int compare(Point o1, Point o2) {
                    return 0;
                }
            });
            for (i = 0; i < res.size(); i++) {//求距离的点 为与i纵坐标的距离在d以内
                for (j = i + 1; j < res.size(); j++) {
                    if (Math.abs(res.get(j).y - res.get(i).y) >= d) {
                        break;
                    }
                    double dp = getDistance(res.get(i), res.get(j));
                    if (dp < d) {
                        d = dp;
                    }
                }
            }
            return d;
        }
    }

    public static void main(String[] args) {
        int j, n;
        Scanner sc = new Scanner(System.in);
        List<Point> list = new ArrayList<Point>();
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            Point p = new Point(sc.nextDouble(), sc.nextDouble());
            list.add(p);
        }
        sc.close();
        list.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                if (o1.x == o2.x) {
                    return (int) (o1.y - o2.y);
                } else {
                    return (int) (o1.x - o2.x);
                }
            }
        });
        System.out.println("所有点之间的最短距离为："+ String.valueOf(getMin((ArrayList<Point>) list, 0, list.size()-1)));
    }

    public static class Point {
        double x;
        double y;
        public Point (double x, double y) {
            this.x = x;
            this.y = y;
        }
    }
}
